#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *求平方根
 * */
//不太会写 挺日的 牛顿迭代和 二分都行
int mySqrt(int x) {
    int low = 0;
    int high = x;
    int res = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        //这里会溢出
        if ((long long) mid * mid <= x) {
            res = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return res;
}